\documentclass[10pt,twocolumn,letterpaper]{article}
\usepackage{cvpr}
\usepackage{times}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{listings}
\usepackage{booktabs}
\usepackage{ctex}
\usepackage{subfigure}
\usepackage{enumerate}
\usepackage{xcolor}
\usepackage{setspace}

% Include other packages here, before hyperref.

% If you comment hyperref and then uncomment it, you should delete
% egpaper.aux before re-running latex.  (Or just hit 'q' on the first latex
% run, let it finish, and you should be clear).
\usepackage[breaklinks=true,bookmarks=true]{hyperref}

\cvprfinalcopy % *** Uncomment this line for the final submission

\def\cvprPaperID{****} % *** Enter the CVPR Paper ID here
\def\httilde{\mbox{\tt\raisebox{-.5ex}{\symbol{126}}}}

% Pages are numbered in submission mode, and unnumbered in camera-ready
%\ifcvprfinal\pagestyle{empty}\fi
\setcounter{page}{1}

\newcommand{\cnabstractname}{摘要}
\newenvironment{cnabstract}{%
	\par 
	\noindent\mbox{}\hfill{\bfseries \cnabstractname}\hfill\mbox{}\par
	\vskip 2.5ex}{\par\vskip 2.5ex}


\linespread{1.2}
\zihao{5}
\setlength{\parindent}{2em}

\setmainfont{Times New Roman}

\begin{document}

%%%%%%%%% TITLE
\title{HOMEWORK 1: Exercises for Monte Carlo Methods}

\author{
18324061\quad 文君逸\\
Lectured by 梁上松, Sun Yat-sen University
}

\maketitle
%\thispagestyle{empty}


%%%%%%%%% ABSTRACT

\section{Exercise 1}

\subsection{问题描述}

The Monte Carlo method can be used to generate an approximate value of $\pi$. The figure \ref{figure1} shows a unit square with a quarter of a circle inscribed. The area of the square is 1 and the area of the quarter circle is $\pi$/4. Write a script to generate random points that are distributed uniformly in the unit square. The ratio between the number of points that fall inside the circle (red points) and the total number of points thrown (red and green points) gives an approximation to the value of $\pi$/4. This process is a Monte Carlo simulation approximating pi. Let N be the total number of points thrown. When N=50, 100, 200, 300, 500, 1000, 5000, what are the estimated $\pi$ values, respectively? For each N, repeat the throwing process 100 times, and report the mean and variance. Record the means and the corresponding variances in a table. 

蒙特卡洛方法可以用于产生接近$\pi$的近似值。图\ref{figure1}显示了一个带有1/4内切圆在内的边长为1的正方形。正方形的面积是1，该1/4圆的面积为$\pi$/4。通过编程实现在这个正方形中产生均匀分布的点。落在圈内（红点）的点和总的投在正方形（红和绿点）上的点的比率给出了$\pi$/4的近似值。这一过程称为使用蒙特卡洛方法来仿真逼近$\pi$实际值。令N表示总的投在正方形的点。当投点个数分别是20, 50, 100, 200, 300, 500, 1000, 5000时，$\pi$值分别是多少？对于每个N，每次实验算出$\pi$值，重复这个过程20次，并在表中记下均值和方差。

\begin{figure}
	\centering
	\includegraphics[scale=0.5]{./1.png}
	\caption{逼近$\pi$的例子}
	\label{figure1}
\end{figure}

\subsection{问题解答}

本题的编程关键点在于产生区间$[0,1]$的随机数。假设一个点的坐标是$(x_{i},y_{i})$，如果$x_{i}^{2}+y_{i}^{2}\leqslant 1$，这个点就是圆内一点，否则为圆外一点。\\

\begin{figure}
	\subfigure[20个点]{ 
		\includegraphics[width=0.47\linewidth]{./20.png} 
	} 
	\subfigure[100个点]{
		\includegraphics[width=0.47\linewidth]{./100.png} 
	} 
	\subfigure[1000个点]{ 
		\includegraphics[width=0.47\linewidth]{./1000.png} 
	} 
	\subfigure[5000个点]{ 
		\includegraphics[width=0.47\linewidth]{./5000.png} 
	} 
	\caption{投掷法实验图像}
	\label{e1}
\end{figure}

\begin{table}
	\caption{$\pi$的估计实验结果}
	
	\label{pi_cal}
	\centering
	
	\begin{tabular*}{\hsize}{@{\extracolsep{\fill}}c c c c} %{\hsize}使三线表自适应宽度，c表示文本居中
		\hline
		点的个数$N$ & $\pi$的估测均值 & 方差\\
		\hline 
		20 & 3.1500 & 0.0139 \\
		50 &  3.1760 & 0.0041 \\
		100 & 3.1640 &  0.0023 \\
		200 & 3.1410 & 0.00069 \\
		300 & 3.1467 & 0.00061 \\
		500 & 3.1420 & 0.00028 \\
		1000 & 3.1408 & 0.000205\\
		5000 & 3.1431 & 0.000036\\
		\hline
	\end{tabular*}
\end{table}

\begin{figure}
	\subfigure[$\pi$的预测]{ 
		\includegraphics[width=0.47\linewidth]{./pre_pi.png} 
	} 
	\subfigure[方差变化]{ 
		\includegraphics[width=0.47\linewidth]{./var1.png} 
	} 
	\caption{投掷法实验图像}
	\label{e2}
\end{figure}

图\ref{e1}是第一题的实验图像，图\ref{e2}是第一题不同$N$值$\pi$的预测和方差变化图像，表\ref{pi_cal}是$\pi$的计算结果和不同$N$值下的方差统计。

\section{Exercise 2}

\subsection{问题描述}

We are now trying to integrate the another function by Monte Carlo method:$$\int_{0}^{1}x^{3}dx$$A simple analytic solution exists here: $\int_{0}^{1}x^{3}dx = \frac{1}{4}$.If you compute this integration using Monte Carlo method, what distribution do you use to sample $x$? How good do you get when N = 5, 10, 20, 30, 40, 50, 60, 70, 80, 100, respectively? For each N, repeat the Monte Carlo process 100 times, and report the mean and variance of the integrate in a table.

我们现在尝试通过蒙特卡洛的方法求解如下的积分：$$\int_{0}^{1}x^{3}dx$$该积分的求解我们可以直接求解，即有$\int_{0}^{1}x^{3}dx = \frac{1}{4}$。如果你用蒙特卡洛的方法求解该积分，你认为$x$可以通过什么分布采样获得？如果采样次数是分别是N = 5, 10, 20, 30, 40, 50, 60, 70, 80, 100，积分结果有多好？对于每个采样次数N，重复蒙特卡洛过程100次，求出均值和方差，然后在表格中记录对应的均值和方差。



\subsection{问题解答}

由于题目要求对$x$进行采样，易知需要用期望法求解本题。期望法的步骤为：假设要计算的积分具有如下形式：$$I=\int_{a}^{b}g(x)dx$$其中被积函数$g(x)$在区间$[a,b]$可积。选取一个概率函数$f_{X}$，满足下列条件:

\begin{enumerate}[(1)]
	\item $g(x)\neq0$时，$f_{X}(x)\neq 0$在$[a,b]$恒成立
	\item $\int_{a}^{b}f_{X}(x)=1$
\end{enumerate}

此时如果记

\begin{equation}
	g^{*}(x)=
	\begin{cases}
		\frac{g(x)}{f_{X}(x)}& f_{X}(x)\neq 0\\
		0& f_{X}(x)=0
	\end{cases}
	\nonumber 
\end{equation}

那么原积分可以写成$$I=\int_{a}^{b}g^{*}(x)f_{X}(x)dx$$

通过生成服从分布律$f_{X}$的随机变量$X_{i}(i=1,2,\cdots ,N)$，通过计算均值$$\bar{I}=\frac{1}{N}\sum_{i=1}^{N}g^{*}(X_{i})$$

作为原积分$I$的近似值，即$\bar{I}\approx I$。就本题而言，由于积分上下限均为有限值，因此$f_{X}$可取均匀分布，即

\begin{equation}
	f_{X}(x)=
	\begin{cases}
		\frac{1}{b-a}& a\leqslant x\leqslant b\\
		0& \text{otherwise}
	\end{cases}
	\nonumber 
\end{equation}

在本题中$a=0,b=1$。表\ref{m1}是计算过程中的统计结果，图\ref{e3}是计算过程的实验图像。

\begin{table}
	\caption{蒙特卡洛方法计算$\int_{0}^{1}x^{3}dx$结果}
	
	\label{m1}
	\centering
	
	\begin{tabular*}{\hsize}{@{\extracolsep{\fill}}c c c c} %{\hsize}使三线表自适应宽度，c表示文本居中
		\hline
		采样个数$N$ & 计算结果 & 方差\\
		\hline 
		5 & 0.2325 & 0.0144 \\
		10 &   0.2581 & 0.0076 \\
		20 & 0.2511 &  0.0035 \\
		30 & 0.2427 &  0.0021 \\
		40 & 0.2449 & 0.0018 \\
		50 & 0.2508 & 0.0014 \\
		60 & 0.2504 & 0.0010\\
		70 & 0.2460 & 0.00091 \\
		80 & 0.2513 & 0.00089\\
		100& 0.2501 & 0.00074\\
		\hline
	\end{tabular*}
\end{table}

\begin{figure}
	\subfigure[积分值预测]{ 
		\includegraphics[width=0.47\linewidth]{./pre_2.png} 
	} 
	\subfigure[方差变化]{ 
		\includegraphics[width=0.47\linewidth]{./var2.png} 
	} 
	\caption{蒙特卡洛方法计算$\int_{0}^{1}x^{3}dx$实验图像}
	\label{e3}
\end{figure}

\section{Exercise 3}

\subsection{问题描述}

We are now trying to integrate a more difficult function by Monte Carlo method that may not be analytically computed:$$\int_{x=2}^{4}\int_{y=-1}^{1}f(x,y)=\frac{y^{2} e^{-y^{2}}+x^{4} e^{-x^{2}}}{x e^{-x^{2}}}$$Can you compute the above integration analytically? If you compute this integration using Monte Carlo method, what distribution do you use to sample $(x,y)$? How good do you get when the sample sizes are N = 5, 10, 20, 30, 40, 50, 60, 70, 80, 100, 200 respectively? For each N, repeat the Monte Carlo process 100 times, and report the mean and variance of the integrate.

我们现在尝试通过蒙特卡洛的方法求解如下的更复杂的积分：$$\int_{x=2}^{4}\int_{y=-1}^{1}f(x,y)=\frac{y^{2} e^{-y^{2}}+x^{4} e^{-x^{2}}}{x e^{-x^{2}}}$$你能够通过公式直接求解上述的积分吗？如果你用蒙特卡洛的方法求解该积分，你认为$(x, y)$可以通过什么分布采样获得？如果点$(x,y)$的采样次数是分别是N = 10, 20, 30, 40, 50, 60, 70, 80, 100, 200, 500, 积分结果有多好？对于每个采样次数N，重复蒙特卡洛过程100次，求出均值和方差，然后在表格中记录对应的均值和方差。

\subsection{问题解答}

很显然无法直接用积分公式求出其原函数进行求解，因此只能通过蒙特卡洛方法近似求解。整体思路仍然沿用上一题的思路，此时随机变量$(x_{i},y_{i})$的生成可以通过$[2,4]\times[-1,1]$上的均匀分布来生成$N$个样本点。表\ref{m2}是计算过程中的统计结果，图\ref{e4}是计算过程中的实验图像。

\begin{table}
	\caption{蒙特卡洛方法计算二重积分结果}
	
	\label{m2}
	\centering
	
	\begin{tabular*}{\hsize}{@{\extracolsep{\fill}}c c c c} %{\hsize}使三线表自适应宽度，c表示文本居中
		\hline
		采样个数$N$ & 计算结果 & 方差 \\
		\hline 
		10 &   113897.186239446 &11561081940.2226 \\
		20 & 117607.694125394 &  5567512006.41676 \\
		30 & 116443.087854190 &  3497285325.74579 \\
		40 & 115525.075557651 & 3096702480.01630 \\
		50 & 114852.555763246 & 2491456904.18493 \\
		60 &  113109.187657963 & 1676615773.53758	\\
		70 &  113483.723231203 & 1563490650.79654 \\
		80 & 115291.185091576 & 1356233135.57202 \\
		100& 112976.286281471 & 1016058692.58522 \\
		200& 112864.514806796 & 735185901.469738 \\
		500& 113148.511291621 & 180780979.148021\\
		\hline
	\end{tabular*}
\end{table}

\begin{figure}
	\subfigure[积分值预测]{ 
		\includegraphics[width=0.47\linewidth]{./pre_3.png} 
	} 
	\subfigure[方差变化]{ 
		\includegraphics[width=0.47\linewidth]{./var_3.png} 
	} 
	\caption{蒙特卡洛方法计算二重积分实验图像}
	\label{e4}
\end{figure}

\section{总结}

通过实验数据可以看到，随着采取的样本点的增多，近似结果往往都能逼近并收敛与真实值附近，而计算方差整体呈下降趋势，且最后接近于0。这也就告诉我们在使用蒙特卡洛方法时要采样尽可能多的数据点并多次求解取平均值，以避免偶然性。

通常蒙特卡罗模拟通过构造符合一定规则的随机数来解决数学上的各种问题。蒙特卡罗方法由于能够真实地模拟实际物理过程，故解决问题与实际非常符合，可以得到很圆满的结果。对于那些由于计算过于复杂而难以得到解析解或者根本没有解析解的问题，蒙特卡罗模拟是一种有效的求出数值解的方法。




\end{document}
